use std::collections::VecDeque;

// 329 Longest Increasing Path in a Matrix
fn longest_increasing_path_topological(matrix: Vec<Vec<i32>>) -> i32 {
    // 计算矩阵每个点的出度，出度被定义为，相邻点中，值大于自身的点的个数
    let (rows, columns) = (matrix.len(), matrix[0].len());
    let mut degree: Vec<Vec<i32>> = vec![vec![0; columns]; rows];
    let dirs = vec![vec![0, 1], vec![1, 0], vec![-1, 0], vec![0, -1]];
    for i in 0..rows {
        for j in 0..columns {
            for dir in dirs.iter() {
                let ii = i as i32 + dir[0];
                let jj = j as i32 + dir[1];
                if ii >= 0 && ii < rows as i32 && jj >= 0 && jj < columns as i32 
                        && matrix[i as usize][j as usize] < matrix[ii as usize][jj as usize] {
                    degree[i][j] += 1;
                }
            }
        }
    }
    // 使用拓扑排序计算层数
    let mut queue: VecDeque<(usize, usize)> = VecDeque::new();
    for i in 0..rows {
        for j in 0..columns {
            if degree[i][j] == 0 {
                queue.push_back((i, j));
            }
        }
    }
    let mut lev: i32 = 0;
    while !queue.is_empty() {
        lev += 1;
        let lev_size = queue.len();
        for _ in 0..lev_size {
            let point = queue.pop_front().unwrap();
            for dir in dirs.iter() {
                let ii = point.0 as i32 + dir[0];
                let jj = point.1 as i32 + dir[1];
                if ii >= 0 && ii < rows as i32 && jj >= 0 && jj < columns as i32 
                            && matrix[point.0 as usize][point.1 as usize] > matrix[ii as usize][jj as usize] {
                    degree[ii as usize][jj as usize] -= 1;
                    if degree[ii as usize][jj as usize] == 0 {
                        queue.push_back((ii as usize, jj as usize));
                    }
                }
            }
        }
    }
    lev
}

fn longest_increasing_path_dfs_memo(matrix: Vec<Vec<i32>>) -> i32 {
    let mut memo : Vec<Vec<i32>> = vec![vec![0; matrix[0].len()]; matrix.len()];
    let mut max_length = 1;
    for i in 0..matrix.len() {
        for j in 0..matrix[0].len() {
            max_length = max_length.max(dfs_memo(&matrix, i as i32, j as i32, &mut memo));
        }
    }
    return max_length;
}

// rethink
fn dfs_memo(matrix: &Vec<Vec<i32>>, i: i32, j: i32, memo: &mut Vec<Vec<i32>>) -> i32 {
    if memo[i as usize][j as usize] != 0 {
        return memo[i as usize][j as usize];
    }
    let dir = vec![vec![0, 1], vec![1, 0], vec![-1, 0], vec![0, -1]];
    memo[i as usize][j as usize] += 1;
    for delta in dir.iter() {
        let ii = i + delta[0];
        let jj = j + delta[1];
        if ii >= 0 && ii < matrix.len() as i32 && jj >= 0 && jj < matrix[0].len() as i32 
                && matrix[i as usize][j as usize] < matrix[ii as usize][jj as usize] {
            memo[i as usize][j as usize] = memo[i as usize][j as usize].max(dfs_memo(matrix, ii, jj, memo) + 1);
        }
    }
    return memo[i as usize][j as usize];
}

fn longest_increasing_path_dfs(matrix: Vec<Vec<i32>>) -> i32 {
    let mut visited : Vec<Vec<bool>> = vec![vec![false; matrix[0].len()]; matrix.len()];
    let mut max_length = 0;
    for i in 0..matrix.len() {
        for j in 0..matrix[0].len() {
            visited[i][j] = true;
            max_length = max_length.max(dfs(&matrix, i as i32, j as i32, 1, &mut visited));
            visited[i][j] = false;
        }
    }
    max_length
}

// return the longest length of path started at (i, j)
fn dfs(matrix: &Vec<Vec<i32>>, i: i32, j: i32, length: i32, visited: &mut Vec<Vec<bool>>) -> i32 {
    let dir = vec![vec![0, 1], vec![1, 0], vec![-1, 0], vec![0, -1]];
    let mut max_length = length;
    for delta in dir.iter() {
        let ii = i + delta[0];
        let jj = j + delta[1];
        if ii < 0 || ii >= matrix.len() as i32 || jj < 0 || jj >= matrix[0].len() as i32 {
            continue;
        }
        if visited[ii as usize][jj as usize] {
            continue;
        }
        if matrix[ii as usize][jj as usize] > matrix[i as usize][j as usize] {
            visited[ii as usize][jj as usize] = true;
            max_length = max_length.max(dfs(matrix, ii, jj, length + 1, visited));
            visited[ii as usize][jj as usize] = false;
        }
    }

    max_length
}

#[test]
fn test_longest_increasing_path() {
    let matrix = vec![
        vec![9,9,4],
        vec![6,6,8],
        vec![2,1,1],
    ];
    // println!("{}", longest_increasing_path_dfs_memo(matrix.clone()));
    println!("{}", longest_increasing_path_topological(matrix));
}